/*
 * CS600 Homework #1 
 * - Merge Sort (Always ascending case)
 * by Shoufu Luo, 2/02/2012
 *
 */

#include "sort.h"
#include "merge.h"
#include "stdio.h"

static void
merge(hw1type *A, int l, int m, int r)
{
	int llen = m - l + 1;
	int rlen = r - m;
	int i, j, k;

	if (l < 0 || m < 0 || r < 0 || rlen < 0 || rlen < 0)
		return;

	hw1type *left_ay = new hw1type[llen];
	hw1type *right_ay = new hw1type[rlen];

	for (i = 0; i < llen; i++)
	{
		assign(left_ay[i], A[l + i]);
	}
	for (j = 0; j < rlen; j++) 
	{
		assign(right_ay[j], A[m + 1 + j]);
	}

	i = j = k = 0;
	while (i < llen && j < rlen)
	{
		if (compare(left_ay[i], right_ay[j]) == 1)
		{
			assign(A[l + k++], right_ay[j++]);
		} 
		else 
		{
			assign(A[l + k++], left_ay[i++]);
		}
	}	

	if (j == rlen)// copy the rest of the left array 
	{
		while (i < llen)
		{
			assign(A[l + k++], left_ay[i++]);
		}
	}

	if (i == llen) // copy the rest of the right array 
	{
		while (j < rlen) 
		{
			assign(A[l + k++], right_ay[j++]);
		}
	}
	delete[] left_ay;
	delete[] right_ay;
}

void
merge_sort(hw1type *A, int l, int r)
{
	int m;

	if (l < r) {
		m = (l + r) / 2;
		merge_sort(A, l, m);
		merge_sort(A, m+1, r);
		merge(A, l, m, r);
	}
}

#include "insert.h"

void
merge_sort(hw1type *A, int l, int r, int k)
{
	int m;

	//printf("-------------------->\n");
	//print_array(A, l, r);
	if (l < r)
	{
		if (r - l <= k)
		{
			insert_sort(A, l, r);				
		} else {
			m = (l + r) / 2;
			merge_sort(A, l, m, k);
			merge_sort(A, m+1, r, k);
			merge(A, l, m, r);
		}
	}
	//printf("--------------------\n");
	//print_array(A, l, r);
	//printf("<--------------------\n");
}
